package exams.array;

import java.util.*;

public class SearchSolution {
    /**
     * 腐烂的橘子
     *
     * 在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
     * 值 0 代表空单元格；
     * 值 1 代表新鲜橘子；
     * 值 2 代表腐烂的橘子。
     * 每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
     * 返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
     * 提示：
     * m == grid.length
     * n == grid[i].length
     * 1 <= m, n <= 10
     * grid[i][j] 仅为 0、1 或 2
     * */
    public int orangesRotting(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int freshOraCount = 0;
        int res = 0;
        ArrayDeque<int[]> queue = new ArrayDeque<>();
        for(int i=0; i<m; i++) {
            for(int j=0;j<n;j++){
                if(grid[i][j] == 2) {
                    queue.add(new int[]{i,j});
                }
                if(grid[i][j] == 1) {
                    freshOraCount++;
                }
            }
        }

        while (!queue.isEmpty()) {
            int size = queue.size();
            for(int i=0; i<size;i++) {
                int[] cur = queue.poll();
                int x = cur[0];
                int y = cur[1];
                // left
                if(y > 0 && grid[x][y - 1] == 1) {
                    freshOraCount --;
                    grid[x][y-1] = 2;
                    queue.add(new int[]{x, y-1});
                }
                // up
                if(x > 0 && grid[x-1][y] == 1) {
                    freshOraCount --;
                    grid[x-1][y] = 2;
                    queue.add(new int[]{x-1, y});
                }
                // right
                if(y < n - 1 && grid[x][y+1] == 1) {
                    freshOraCount --;
                    grid[x][y+1] = 2;
                    queue.add(new int[]{x, y+1});
                }
                // down
                if(x < m - 1 && grid[x+1][y] == 1) {
                    freshOraCount --;
                    grid[x+1][y] = 2;
                    queue.add(new int[]{x+1, y});
                }
            }
            res++;
        }

        if(freshOraCount > 0) {
            return -1;
        }

        return res > 0? res - 1: res;
    }


    /**
     * 岛屿数量
     * 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
     * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
     * 此外，你可以假设该网格的四条边均被水包围。
     * */
    public int numIslands(char[][] grid) {
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == '1') {
                    res++;
                    dfs(grid, i, j);
                }
            }
        }

        return res;
    }

    private void dfs(char[][] grid, int x, int y) {
        if(x > 0 && y > 0 && x < grid.length && y < grid[x].length && grid[x][y] == '1') {
            grid[x][y] = '0';
            dfs(grid, x, y - 1);
            dfs(grid, x - 1, y);
            dfs(grid, x, y + 1);
            dfs(grid, x + 1, y);
        }
    }

    /**
     * n * m 数组填有 A-Z 字母
     * 求能否找到子字符串，返回字符串首字母所在位置
     *
     * ABCDEFG
     * BAAHELL
     * OOOOOLO
     * DDDDDDD
     *
     * 找到HELLO，返回H所在位置，只能上下左右找下一个，不能回头
     * */
    public int[] findWord(String word, char[][] matrix) {
        int[] res = {-1, -1};
        for(int i =0; i<matrix.length; i++) {
            for(int j=0; j<matrix[i].length; j++) {
                if(word.charAt(0) == matrix[i][j]) {
                    boolean[][] visited = new boolean[matrix.length][matrix[i].length];
                    if(dfs(word, matrix, visited, i ,j, 0)) {
                        res[0] = i;
                        res[1] = j;
                    }
                }
            }
        }
        return res;
    }

    private boolean dfs(String word, char[][] matrix, boolean[][] visited, int x, int y, int index) {
        if(index == word.length()) {
            return true;
        }
        if(x < 0 || y < 0 || x > matrix.length - 1 || y > matrix[x].length - 1 || visited[x][y]) {
            return false;
        }
        visited[x][y] = true;
        if(matrix[x][y] == word.charAt(index)) {
            if(dfs(word, matrix, visited, x, y-1, index + 1) ||
                dfs(word, matrix, visited, x-1, y, index + 1) ||
                dfs(word, matrix, visited, x, y + 1, index + 1) ||
                dfs(word, matrix, visited, x + 1, y, index + 1)
            ) {
                return true;
            }
        } else {
            visited[x][y] = false;
            return false;
        }

        visited[x][y] = false;
        return false;
    }



}


